package 链表;

/**
 * @Author zxl
 * @Date 2022/1/15 20:08
 * @Desc 判断一个链表是否有环，如果有环，则找到入环的第一个节点，如果无环，则返回NULL
 * 解题：快慢指针，fast指针每次移动两个位置，slow指针每次移动一个位置
 *  1. 判断链表是否有环
 *      1>. 如果相遇一定是在环中相遇：因为fast指针一定先进入到环中，之后便一直在环中跑，如果slow要遇到fast,则一定是在环中相遇
 *      2>. fast一定会和slow相遇，并且fast不会跨国slow,因为fast步长为2，slow步长为1，所以fast和slow的相对距离在一步步的减少，直至相遇
 *  2. 寻找环的入口
 *      假设从头节点到环入口的节点数是x，环的入口到指针相遇节点的节点数是y，从相遇节点再到环的入口的节点数是z，
 *      则，当fast指针和slow指针相遇时候，slow移动了x+y个节点，fast移动了x+y+n(z+y)，n表示fast在环内移动了n圈
 *      因为fast步长是slow的2倍 => 2(x+y)=x+y+n(z+y) => x+y=n(z+y) => x=n(z+y)-y => x=(n-1)(y+z)+z
 *      由公式x=(n-1)(y+z)+z可知，当n=1时，x=z，相当于这时候相遇的地方就是环的入口
 *                               当n>1时，fast在环内走了n圈才遇到slow，这时候依然是在环入口相遇
 *      由上推断可知，如果指针index1从头节点开始移动，指针index2从y节点位置开始移动（相当于提前走了y步），两个指针的步长都是1，
 *      则两个指针一定在环入口相遇，index走了n圈
 */
public class 判断链表是否有环 {

    /**
     * 初始化链表
     * @return
     */
    public static Node initData(){
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;
        Node node5 = new Node();
        node5.value = 5;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next=node3;
        return node1;
    }

    public static void main(String[] args) {

        Node entryCycle = findCycleEntry(initData());
        System.out.println("结果：" + (entryCycle == null ? "NULL" : entryCycle.value));
    }

    public static Node findCycleEntry(Node head){
        Node fast = head;
        Node slow = head;
        while (fast != null && fast.next != null){
            // 说明有环
            slow = slow.next;
            fast = fast.next.next;
            // 相遇
            if (fast.equals(slow)){
                Node index1 = head;
                Node index2 = fast;
                // 找入口
                while (index1.value != index2.value){
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index2;
            }
        }
        // 说明没有环
        return null;

    }
}
